package main.leetcode.offer.firstround.from03to50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 38.字符串的排列
 *
 * <p>输入一个字符串，打印出该字符串中字符的所有排列。
 *
 * <p>你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 * <p>
 *
 * <p>示例:输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
 *
 * <p>限制：1 <= s 的长度 <= 8
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex38 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new ex38().permutation("abc")));
    }

    // 自己瞎想的法子
    //  public String[] permutation(String s) {
    //    if (s.length() == 1) return new String[] {s};
    //    Set<String> set = new HashSet<>();
    //    set.add("" + s.charAt(0));
    //    permutation(set, s, 1);
    //    return set.toArray(new String[0]);
    //  }
    //
    //  private void permutation(Set<String> set, String s, int i) {
    //    if (i > s.length() - 1) return; // 已经到最后一位
    //    String[] res = set.toArray(new String[0]); // 保存i-1位的保存结果
    //    set.clear(); // 清空i-1位的排序结果
    //    int n = res[0].length(), j;
    //    String pre, post;
    //    for (String str : res) { // 遍历i-1位的所有遍历结果，每个结果再依次插入第i个字符
    //      set.add(str + s.charAt(i)); // 插在首尾
    //      set.add(s.charAt(i) + str); // 插在尾部
    //      for (j = 1; j < n; j++) { // 插入中间所有可能的位置
    //        pre = str.substring(0, j);
    //        post = str.substring(j, n);
    //        set.add(pre + s.charAt(i) + post);
    //      }
    //    }
    //    permutation(set, s, i + 1);
    //  }
    public String[] permutation(String s) {
        int n = s.length();
        if (n == 1) return new String[] {s};
        ArrayList<String> res = new ArrayList<>();
        boolean[] isUsed = new boolean[n];
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        dfs(cs, n, 0, isUsed, res, new StringBuilder());
        return res.toArray(new String[0]);
    }

    private void dfs(
            char[] data, int n, int i, boolean[] isUsed, List<String> res, StringBuilder s) {
        if (i == n) {
            res.add(s.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (isUsed[j] || j > 0 && data[j] == data[j - 1] && !isUsed[j - 1]) continue;
            s.append(data[j]);
            isUsed[j] = true;
            dfs(data, n, i + 1, isUsed, res, s);
            isUsed[j] = false;
            s.deleteCharAt(s.length() - 1);
        }
    }
}
